/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/merge-intervals
   @Language: C++
   @Datetime: 19-06-20 13:18
   */

// Method 1, copy
class Solution {
	static bool less(const vector<int> &a, const vector<int> &b){
		if(a[0]!=b[0]) return a[0]<b[0];
		else return a[1]<b[1];
	}
public:
	vector<vector<int> > merge(vector<vector<int> > &intervals) {
		if(intervals.size()==0) return intervals;
		sort(intervals.begin(),intervals.end(),less);
		vector<vector<int> > vs(1,intervals[0]);
		for(int i=1; i<intervals.size(); ++i){
			auto &a=vs.back(), &b=intervals[i];
			if(a[1]>=b[0]) a[1]=max(a[1],b[1]);
			else vs.push_back(b);
		}
		return vs;
	}
};

// Method 2, inpalce
class Solution {
	static bool less(const vector<int> &a, const vector<int> &b){
		if(a[0]!=b[0]) return a[0]<b[0];
		else return a[1]<b[1];
	}
public:
	vector<vector<int> > merge(vector<vector<int> > &intervals) {
		if(intervals.size()<2) return intervals;
		sort(intervals.begin(),intervals.end(),less);
		int len=1;
		for(int i=1; i<intervals.size(); ++i){
			auto &a=intervals[len-1], &b=intervals[i];
			if(a[1]>=b[0]) a[1]=max(a[1],b[1]);
			else intervals[len++]=b;
		}
		intervals.erase(intervals.begin()+len,intervals.end());
		return intervals;
	}
};
